Enterprises and individual users are using distributed storage systems (i.e., cloud storage services) to store data on memory overlying multiple memory locations. Many of these enterprises and individuals encrypt their data before uploading the data onto the distributed storage system. In order to use essential functionalities offered by the cloud storage services, such as performing search queries on stored data, enterprises are required to provide plaintext access to the cloud storage services. As a result, some government and sensitive private sectors, such as health, finance, and legal may be reluctant to use cloud storage services, despite their increased convenience and cost advantages. Additionally, encryption alone may not suffice for ensuring data privacy, as the mere knowledge of data access patterns can provide a significant amount of information about the data without ever needing to decrypt the data.